#include <vector>

using namespace std;

// 分割数组的最大值(画匠问题)
// 给定一个非负整数数组 nums 和一个整数 m
// 你需要将这个数组分成 m 个非空的连续子数组。
// 设计一个算法使得这 m 个子数组各自和的最大值最小。
// 测试链接 : https://leetcode.cn/problems/split-array-largest-sum/

class Solution 
{
private:
    int f(vector<int>& nums, long limit)
    {
        int parts = 1;
        int sum = 0;
        for(int x : nums)
        {
            if(x > limit) return INT_MAX;
            else if(sum + x > limit)
            {
                ++parts;
                sum = x;
            }
            else
            {
                sum += x;
            }
        }
        return parts;
    }

public:
    // 时间复杂度 O(n * log(sum))，额外空间复杂度 O(1)
    int splitArray(vector<int>& nums, int k) 
    {
        long sum = 0;
        for(int x : nums) sum += x;
        long l = 0, r = sum, ans = 0;
        while(l <= r)
        {
            long m = l + ((r - l) >> 1);
            // 必须让数组每一部分的累加和 <= m，请问划分成几个部分才够!
            long need = f(nums, m);
            if(need <= k)
            {
                // 达标
                ans = m;
                r = m - 1;
            }
            else
            {
                // 不达标
                l = m + 1;
            }
        }
        return ans;
    }
};